package hot100;


/*
 * Author：江松
 * Date：2023/4/6 15:23
 *
 *
 滑动窗口的最大值:
 1，暴力
 2，维护窗口，单调队列：
 如果后面加入的数更大，则前面如队的数就没有存在价值了（队头最大的递减队列）
 同时要判断队头是否过期，因此使用队列存储下标
 */

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Main239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n=nums.length;
        int size=n-k+1;
        Deque<Integer>q=new LinkedList<>();
        int res[]=new int[size];
        int cnt=0;
        for(int i=0;i<n;++i){
            while(!q.isEmpty()&&nums[q.peekLast()]<nums[i]){
                q.pollLast();
            }
            q.offerLast(i);
            //判断过期
            if(i>=q.peekFirst()+k){
                q.pollFirst();
            }
            if(i>=k-1){
                res[cnt++]=nums[q.peekFirst()];
            }
        }
        return res;
    }
}
